import java.util.*;

public class GraphLoopTest {
    private Map<String, List<String>> graph = new HashMap<String, List<String>>();
    public static void main(String[] args) {
        GraphLoopTest test = new GraphLoopTest();
        test.initGraphData();//初始化图
        test.BFSSearch("1");//从1开始一连串的遍历
    }

    /**
     * 初始化图数据：使用邻居表来表示图数据。
     */
    public void initGraphData() {
//        图结构如下
//          1
//        /   \
//       2     3
//      / \   / \
//     4  5  6  7
//      \ | / \ /
//        8    9
//        asList将数组转化为列表，数组和列表就链接在一起了，更新其中之一，另一个随之更新
        graph.put("1", Arrays.asList("2", "3"));
        graph.put("2", Arrays.asList("1", "4", "5"));
        graph.put("3", Arrays.asList("1", "6", "7"));
        graph.put("4", Arrays.asList("2", "8"));
        graph.put("5", Arrays.asList("2", "8"));
        graph.put("6", Arrays.asList("3", "8", "9"));
        graph.put("7", Arrays.asList("3", "9"));
        graph.put("8", Arrays.asList("4", "5", "6"));
        graph.put("9", Arrays.asList("6", "7"));
    }

    /**
     * 广度优先搜索(BFS, Breadth First Search)
     * BFS使用队列(queue)来实施算法过程
     */
    private Queue<String> queue = new LinkedList<String>();//记录数组元素
    private Map<String, Boolean> status = new HashMap<String, Boolean>();//记录是否遍历过，true or false

    public void BFSSearch(String startPoint) {
        //1.把起始点放入queue；
        queue.add(startPoint);
        status.put(startPoint, false);
        bfsLoop();
    }

    private void bfsLoop() {
        //  1) 从queue中取出队列头的点；更新状态为已经遍历。
        String currentQueueHeader = queue.poll(); //出队
        status.put(currentQueueHeader, true);//置为true
        System.out.print(currentQueueHeader+" ");//输出
        //  2) 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入queue中。
        List<String> neighborPoints = graph.get(currentQueueHeader);//?????
        for (String poinit : neighborPoints) {//增强for循环 遍历neighborPoints
            if (!status.getOrDefault(poinit, false)) { //未被遍历
                if (queue.contains(poinit)) continue;
                queue.add(poinit);
                status.put(poinit, false);
            }
        }
        if (!queue.isEmpty()) {  //如果队列不为空继续遍历
            bfsLoop();
        }
    }
}